#include <iostream>
#include <list>
#include <vector>

std::list<int> fibo_it(int n)
{
	std::list<int> fibo;
	int prev = 1;
	int prevprev = 1;
	int cur;
	for(int i=0; i<n; i++) {
		if (i == 0 || i == 1) {
			fibo.push_back(1);
			continue;
		}
		cur = prev + prevprev; //fibo[i-1]+fibo[i-2]
		prevprev = prev;
		prev = cur;
		fibo.push_back(cur);
	}
	return fibo;
}

int fibo_rec(int n)
{
	if (0 == n)
		return 1;
	if (1 == n)
		return 1;
	return fibo_rec(n-1) + fibo_rec(n-2);
}

std::vector<int> M;
int fibo_dyn(int n)
{
	if (0 == n) {
		if (M.size() == 0) 
			M.push_back(1);
	}
	else if(1 == n) {
		if (M.size() == 1) 
			M.push_back(1);
	}
	else if (M.size() <= n) {
		int fiboN = fibo_dyn(n-1) + fibo_dyn(n-2);
		std::cout << "n = " << n << " M.size=" << M.size() <<  ". fiboN: " << fiboN << std::endl;
		M.push_back(fiboN);
	}
	
	return M[n];
}


int main(int argc, char*argv[])
{
	std::cout << fibo_rec(5) << std::endl;	
	std::list<int> fibo = fibo_it(8);
	
	std::list<int>::iterator it;
	for(it = fibo.begin(); it != fibo.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
	
	std::cout << fibo_dyn(7) << std::endl;
	
	return 0;
}